home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 6961 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.1 KB  |  54 lines

  1. Path: sun001.spd.dsccc.com!spd!jmccarty
  2. From: jmccarty@spd.dsccc.com (Mike McCarty)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 20 Feb 1996 20:36:15 GMT
  6. Organization: DSC Communications Corporation, Plano, Texas USA
  7. Message-ID: <4gdbbv$l1r@sun001.spd.dsccc.com>
  8. References: <4fr8be$ass@news.iconn.net> <4g0giv$94s@sun132.spd.dsccc.com> <4gbsir$opr@axl02it.ntc.nokia.com>
  9. NNTP-Posting-Host: aplo139.spd.dsccc.com
  10.  
  11. In article <4gbsir$opr@axl02it.ntc.nokia.com>,
  12. Risto Lankinen  <risto.lankinen@ntc.nokia.com> wrote:
  13. )Hi!
  14. )
  15. )kcline@sun132.spd.dsccc.com (Kevin Cline) wrote:
  16. )>In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net>
  17. )>wrote:
  18. )>>Here is what I am trying to do, I want to find the last NON-ZERO digit
  19. )>>of a given factorial.  For instance,
  20. )>>
  21. )>>5! = 120
  22. )>>
  23. )>>so the last non-zero digit is 2. ...
  24. )
  25. )   [a suggested solution deleted]
  26. )
  27. )>This solution runs in O(n).  With a bit more thought a log(n) solution
  28. )>is possible.
  29. )
  30. )There is an algorithm that calculates the last non-zero _binary_ digit
  31. )of ANY factorial - with SUB-LOGARITHMIC time even in the worst case!!!
  32. )
  33. )Mail me if interested but be prepared to explain what you need it for.
  34. )The algorithm is indeed very VERY fast, and so I don't want to give it
  35. )away without being credited at least.  Also, please mention "rightmost
  36. )non-zero binary digit algorithm" in your request.
  37. )
  38. )terv: Risto
  39.  
  40. Through crafty net espionage, I have managed to obtain a copy of
  41. Risto's algorithm. It's truly amazing! He did it with a single line
  42. macro, so it is even automatically inlined! And it is really, really (I
  43. mean really) fast! I am willing to sell copies of this macro to anyone
  44. for $5.00 per person, but only for the first 1000 who ask. Oh, one
  45. condition of sale is: do not under any circumstances let anyone know
  46. where you got the algorithm, especially don't tell Risto, since he
  47. would be angry if he found out that I had penetrated his security.
  48.  
  49. Mike
  50. ----
  51. char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
  52.  
  53. I don't speak for DSC.         <- They make me say that.
  54.